The present invention relates to a routing system for calculating transmission loads on the basis of load information sent from adjacent nodes when data is sent from a self node to other nodes as the adjacent nodes within a network under the assumption that each node has a store and forward function, and for performing routing in units of destination nodes and, more particularly, to a routing system in a computer communication network system using a communication protocol of a message or packet switching type.
In computer networks, a scheme for determining which of the circuits (links) is used to transmit data between computers or terminals (to be referred to as nodes hereinafter) is called routing. One of the routing systems is used in an ARPANET (Advanced Research Project Agency Network). According to this routing system, optimal sequential routing is performed on the basis of changes in loads of circuits and the nodes within the network. In order to realize this system in practice, each node sends load information for routing to adjacent nodes. The load information represents a load for transmitting data from a self or given node to each adjacent node within the network. The load information is obtained by adding a load of the given node and a load of a circuit used for receiving load information from each adjacent node to the load represented by the load information received by each adjacent node. Each node determines a circuit with a minimum data transmission load in units of destination nodes when data is sent to each adjacent node within the network, thus achieving routing.
According to this conventional routing system, when a system failure such as a circuit disconnection causing an abrupt change in network condition occurs, it takes a long period of time to set in each node new load information (routing information) corresponding to such a change. The same data tends to be repeatedly exchanged between given nodes as if they are playing "catch". For example, in a network shown in FIG. 1, assume that a circuit (to be referred to as a link hereinafter) 12-2 for connecting nodes 11-2 and 11-3 is disconnected, which is then detected by node 11-2. In this state, when node 11-2 is to send data to node 11-3, node 11-2 selects link 12-1 since the load of link 12-2 is infinite. In other words, load information is updated and then routing is performed. Data for node 11-3 is sent onto link 12-1. Node 11-1 receives data sent from node 11-2 to node 11-3 through link 12-1, node 11-1 sends this data onto link 12-1 so as to send it to node 11-3. When link 12-2 is disconnected, data for node 11-3 is repeatedly exchanged between nodes 11-1 and 11-2 until the route to the node is discriminated to be absent. As a result, link 12-1 is abnormally overloaded.
In order to solve the above problem in a conventional routing system, the load information is not updated for a predetermined period of time in a node where a link disconnection has been detected. The current load information is made invalid, and control is shifted to higher-level retransmission processing. This period is called "down time". This system is effective in the network shown in FIG. 1. However, in a network having link 12-3 for directly connecting nodes 11-1 and 11-3 shown in FIG. 2, the following problem is posed. In the network shown in FIG. 2, even if link 12-2 is disconnected, it is possible to send data from node 11-2 to node 11-3 through link 12-1, node 11-1, and link 12-3. If the down time is set unconditionally, as described above, data cannot be transmitted during the down time although the data transmission route is present, thus wasting transmission time. However, according to the conventional routing system, it is impossible for node 11-2 to discriminate whether a data transmission route is present between nodes 11-1 and 11-3. Therefore, the down time must be inevitably set unconditionally, as described above.